LeetCode——无重复字符的最长子串

NO.3 无重复字符的最长子串中等

思路一：暴力法 先双层for循环划分出所有子串并依次进行是否含有重复子符的判断，如果不含重复字符且子串长度大于当前count所记录的子串长度值，就更新count：

public int lengthOfLongestSubstring(String s) {
        int count=0;
//        用两个for循环枚举所有子串。
        for (int i=0;i<s.length();i++){
            for (int j=i+1;j<=s.length();j++){
//                调用allUnique方法校验子串中是否都是唯一的字符。
                if (allUnique(s,i,j))
                    count=Math.max(count,j-i);
            }
        }
        return count;
    }
//    校验子串中是否都是唯一的字符。
private boolean allUnique(String s, int start, int end) {
        Set set=new HashSet();
        for (;start<end;start++){
            if (set.contains(s.charAt(start)))return false;
            set.add(s.charAt(start));
        }
        return true;
    }

时间复杂度：O(n^3)

思路二：滑动窗口法 滑动窗口是数组/字符串问题中常用的抽象概念。窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)[i,j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)[i,j) 向右滑动 11 个元素，则它将变为 [i+1, j+1)[i+1,j+1)（左闭，右开）。

1.用一个hashset作为滑动窗口来存储当前窗口 [i , j)。2.检查j索引处的元素是否在已经在滑动窗口set中？3.如果已存在，就将i索引处的元素从滑动窗口中移除，并将i向右滑动一步。4.set中如果不存在j索引元素的重复元素，就将j元素放入滑动窗口中，并将j向右滑动一步，并更新count。

public int lengthOfLongestSubstring(String s) {
          Set set=new HashSet();
          int count=0,i=0,j=0;
          while (i<s.length()&&j<s.length()){
  //            如果s.charAt(j))已经在set中，
              if (set.contains(s.charAt(j))){
//                将i元素从滑动窗口中移除，并将i向右滑动一步。                  
                  set.remove(s.charAt(i++));
              }else {    //s.charAt(j))不在set中，
//                将j元素放入滑动窗口中，并将j向右滑动一步，               
                  set.add(s.charAt(j++));
//                更新count。            
                  count = Math.max(j-i,count);
              }
          }
          return count;
}

时间复杂度：O(n)

优化滑动窗口法：上述方法最坏情况需要执行2n次，我们可以将它减少为执行n次。上述方法中滑动窗口当第j个元素在窗口中发生重复时，就删除第i个元素并且将i向前移动一步，有时候需要i多次移动之后才能使第j个元素不重复。我们可以使用hashmap代替hashset，就可以将元素及其下标组成k-v对存入hashmap，当发生第j个元素重复时，就可以一次将i移动到位：

public int lengthOfLongestSubstring(String s) {
        int count=0;
        Map<Character,Integer> map=new HashMap();
        for (int j=0,i=0;j<s.length();j++){
            char c=s.charAt(j);
//          无论是否更新start，都会更新其map数据结构和结果ans。
            if (map.containsKey(c)){
//              移动到集合中重复字符下标的下一位。
                i=Math.max(i,map.get(c)+1);
            }
            map.put(c,j);
            count=Math.max(j-i+1,count);
        }
        return count;
    }

思路三：预测字符集法 就题说题，针对这道题有一种思路：假设字符集较小（只有字母和符号等等，不含中文等等），我们可以用一个整数数组作为直接的访问表来代替map。例如：假设参数字符集只含有字母’a’-‘z’或’A’-‘Z’，就用一个int[24]来包含所有字符集；假设参数字符集只含有ASCII，就用一个int[128]来包含所有字符集；假设参数字符集只含有扩展ASCII，就用一个int[256]来包含所有字符集。

针对这道题，我们假设字符集只含有ASCII：

public int lengthOfLongestSubstring(String s) {
        int count=0;
//        数组作为直接访问表代替map。
        int[] index=new int[128];
        for (int j=0,i=0;j<s.length();j++){
//            如果index[s.charAt(j)]的值大于i，则说明当前窗口中元素与第j个字符重复了，
//            就让i=index[s.charAt(j)]，使窗口一次性移动到不含重复元素的位置。
            i=Math.max(i,index[s.charAt(j)]);
//            记录窗口中元素个数,如果不重复元素个数大于之前的记录值,就更新count。
            count=Math.max(count,j-i+1);
//            使当前元素作为数组下标并将该元素的下标+1更新至数组,形成类似于hashmap中k-v对的形式。
            index[s.charAt(j)]=j+1;
        }
        return count;
    }

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.3 无重复字符的最长子串 中等

NO.3 无重复字符的最长子串中等